//给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 
//
// 两个相邻元素间的距离为 1 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
//输出：[[0,0,0],[0,1,0],[0,0,0]]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
//输出：[[0,0,0],[0,1,0],[1,2,1]]
// 
//
// 
//
// 提示： 
//
// 
// m == mat.length 
// n == mat[i].length 
// 1 <= m, n <= 10⁴ 
// 1 <= m * n <= 10⁴ 
// mat[i][j] is either 0 or 1. 
// mat 中至少有一个 0 
// 
// Related Topics广度优先搜索 | 数组 | 动态规划 | 矩阵 
//
// 👍 757, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

// 542. 01 矩阵
class Zero1Matrix {
    public static void main(String[] args) {
        Solution solution = new Zero1Matrix().new Solution();
        solution.updateMatrix(new int[][]{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // BFS，和1162一致，添加所有0到队列中，一层一层的寻找1
    /*public int[][] updateMatrix(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++) {
                if (mat[i][j] == 0) queue.offer(new int[]{i, j});
            }
        }

        int count = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                int[] poll = queue.poll();
                int i = poll[0], j = poll[1];
                for (int[] dir : dirs) {
                    int x = i + dir[0];
                    int y = j + dir[1];
                    if (x < 0 || y < 0 || x >= m || y >= n || mat[x][y] == 0 || visited[x][y]) continue;
                    queue.offer(new int[]{x, y});
                    mat[x][y] = count;
                    visited[x][y] = true;
                }
            }

            // 层数加一
            count++;
        }

        return mat;
    }*/

        // DP
        // dp[i][j] 是取四个方向的最小值 + 1，此时就需要4个方向来递推
        // 可以从4个角来推，优化未左上到右下，右下到左上
        // https://leetcode.cn/problems/01-matrix/solution/2chong-bfs-xiang-jie-dp-bi-xu-miao-dong-by-sweetie/
        public int[][] updateMatrix(int[][] mat) {
            int m = mat.length, n = mat[0].length;
            int[][] dp = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j] = mat[i][j] == 0 ? 0 : 10000;
                }
            }

            // 左上到右下
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (i - 1 >= 0) dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j]);
                    if (j - 1 >= 0) dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i][j]);
                }
            }

            // 右下到左上
            for (int i = m - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    if (i + 1 < m) dp[i][j] = Math.min(dp[i + 1][j] + 1, dp[i][j]);
                    if (j + 1 < n) dp[i][j] = Math.min(dp[i][j + 1] + 1, dp[i][j]);
                }
            }


            return dp;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
